package com.csdemos.algs;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Random;
import static com.csdemos.algs.ArrayUtils.swap;;

public class SortUtils {
	
	public static final int NO_SORT = -1;
	public static final int QUICK_SORT = 0;
	public static final int RANDOM_QUICK_SORT = 1;
	public static final int HOARE_QUICK_SORT = 2;
	public static final int HEAP_SORT = 3;
	public static final int COUNTING_SORT = 4;
	public static final int RADIX_SORT = 5;
	public static final int BUCKET_SORT = 6;
	
	private static final Random rand = new Random();
	
	private static void quickSort(int[] array) {
		initQuickSort(array, 0, array.length - 1);
	}
	
    private static void initQuickSort(int[] A, int p, int r) {
		if (p < r) {
			int q = partition(A, p, r);
			initQuickSort(A, p, q - 1);
			initQuickSort(A, q + 1, r);
		}
	}
	
	private static int partition(int[] A, int p, int r) {
		int x = A[r];
		int i = p - 1;
		for (int j = p; j < r; ++j) {
			if (A[j] <= x) {
				++i;
				swap(A, i, j);
			}
		}
		swap(A, i + 1, r);
		return i + 1;
	}
	
	private static void randomQuickSort(int[] array) {
		initRandomQuickSort(array, 0, array.length - 1);
	}
	
    private static void initRandomQuickSort(int[] A, int p, int r) {
    	if (p < r) {
			int q = randomizedPartition(A, p, r);
			initRandomQuickSort(A, p, q - 1);
			initRandomQuickSort(A, q + 1, r);
		}
	}
	
	private static int randomizedPartition(int[] A, int p, int r) {
		int i = p + rand.nextInt(r - p + 1);
		swap(A, r, i);
		return partition(A, p, r);
	}
	
	private static void quickSortHoare(int[] array) {
		initQuickSortHoare(array, 0, array.length - 1);
	}
	
    private static void initQuickSortHoare(int[] A, int p, int r) {
		if (p < r) {
			int q = partitionHoare(A, p, r);
			initQuickSort(A, p, q);
			initQuickSort(A, q + 1, r);
		}
	}
	
	private static int partitionHoare(int[] A, int p, int r) {
		int x = A[p];
		int i = p - 1;
		int j = r + 1;
		while (true) {
			do {
				--j;
			} while (A[j] > x);
			do {
				++i;
			} while (A[i] < x);
			if (i < j) {
				swap(A, i, j);
			} else {
				return j;
			}
		}
	}
	
	static int parent(int i) {
		return i / 2;
	}
	
	static int left(int i) {
		return 2 * i;
	}
	
	static int right(int i) {
		return 2 * i + 1;
	}
	
	static void maxHeapify(int[] A, int i, int heapSize) {
		int l = left(i);
		int r = right(i);
		int largest;
		if (l < heapSize && A[l] > A[i]) {
			largest = l;
		} else {
			largest = i;
		}
		if (r < heapSize && A[r] > A[largest]) {
			largest = r;
		}
		if (largest != i) {
			swap(A, i, largest);
			maxHeapify(A, largest, heapSize);
		}
	}
	
	static int buildMaxHeap(int[] A) {
		int heapSize = A.length;
		for (int i = (A.length - 1) / 2; i >= 0; --i) {
			maxHeapify(A, i, heapSize);
		}
		return heapSize;
	}
	
	static void heapSort(int[] A) {
		int heapSize = buildMaxHeap(A);
		for (int i = A.length - 1; i>= 1; --i) {
			swap(A, 0, i);
			heapSize--;
			maxHeapify(A, 0, heapSize);
		}
	}
	
	private static void countingSort(int[] A, int[] B, int k) {
		int[] C = new int[k];
		for (int j = 0; j < A.length; ++j) {
			++C[A[j]];
		}
		for (int i = 1; i < k; ++i) {
			C[i] += C[i - 1];
		}
		for (int j = A.length - 1; j >= 0; --j) {
			B[C[A[j]] - 1] = A[j];
			--C[A[j]];
		}
	}
	
	private static class IntWrapper {
		int key;
		int originalValue;
		int currentValue;
		
		public IntWrapper(int value) {
			this.originalValue = value;
			this.currentValue = value;
		}
		
		@Override
		public String toString() {
			return "(" + key + ", " + originalValue + ")";
		}
	}
	
	private static void countingSort(IntWrapper[] A, IntWrapper[] B, int k) {
		int[] C = new int[k];
		for (int j = 0; j < A.length; ++j) {
			++C[A[j].key];
		}
		for (int i = 1; i < k; ++i) {
			C[i] += C[i - 1];
		}
		for (int j = A.length - 1; j >= 0; --j) {
			B[C[A[j].key] - 1] = A[j];
			C[A[j].key] -= 1;
		}
	}
	
	private static void radixSort(int[] AA, int d) {
		IntWrapper[] A = new IntWrapper[AA.length];
		IntWrapper[] B = new IntWrapper[AA.length];
		for (int i = 0; i < AA.length; ++i) {
			A[i] = new IntWrapper(AA[i]);
		}
		for (int i = 0; i < d; ++i) {
			for (int j = 0; j < A.length; ++j) {
				IntWrapper currentIntWrapper = A[j];
				currentIntWrapper.key = currentIntWrapper.currentValue % 10;
				currentIntWrapper.currentValue /= 10;
			}
			countingSort(A, B, 10);
			for (int j = 0; j < A.length; ++j) {
				A[j] = B[j];
			}
		}
		for (int i = 0; i < AA.length; ++i) {
			AA[i] = A[i].originalValue;  
		}
	}
	
	private static void bucketSort(double[] A) {
		int n = A.length;
		@SuppressWarnings("unchecked")
		LinkedList<Double>[] B = new LinkedList[n];
		for (int i = 0; i < n; ++i) {
			B[i] = new LinkedList<Double>();
		}
		for (int i = 0; i < n; ++i) {
			B[(int)(n * A[i])].addLast(A[i]);
		}
		LinkedList<Double> sortedList = new LinkedList<Double>();
		for (int i = 0; i < n; ++i) {
			Collections.sort(B[i]);
			sortedList.addAll(B[i]);
		}
		int k = 0;
		for (Double d : sortedList) {
			A[k++] = d;
		}
	}
	
	public static void sort(int[] A, int maxValue, int sortMethod) {
		switch (sortMethod) {
		case QUICK_SORT:
			quickSort(A);
			break;
		case RANDOM_QUICK_SORT:
			randomQuickSort(A);
			break;
		case HOARE_QUICK_SORT:
			quickSortHoare(A);
			break;
		case HEAP_SORT:
			heapSort(A);
			break;
		case COUNTING_SORT:
			int[] B = new int[A.length];
			countingSort(A, B, maxValue);
			for (int i = 0; i < A.length; ++i) {
				A[i] = B[i];
			}
			break;
		case RADIX_SORT:
			radixSort(A, (int)Math.ceil(Math.log10(maxValue)));
			break;
		case BUCKET_SORT:
			int size = A.length;
			double[] D = new double[size];
			for (int i = 0; i < size; ++i) {
				D[i] = (double)A[i] / maxValue;
			}
			bucketSort(D);
			for (int i = 0; i < size; ++i) {
				A[i] = (int)(D[i] * maxValue);
			}
			break;
		}
	}
	
}
